package com.example.dynamicprogramming42;

/**
 * @description 回溯算法,最长公共子串长度
 * 最长公共子串长度的大小，表示两个字符串相似程度的大小
 * @auther lijiewei
 * @date 2022/5/16 16:26
 */
public class ComStrDynamicProgramming {

    /**
     * 状态转移表法求最长公共子串长度
     * @param a 数组a
     * @param n 数组a的长度
     * @param b 数组b
     * @param m 数组b的长度
     * @return
     * @author lijiewei
     * @date   2022/5/17 14:37
     */
    public int lcs(char[] a, int n, char[] b, int m) {
        //二维状态表，操作完a[i],b[j]后的最小值
        int[][] maxlcs = new int[n][m];
        //初始化第0行
        for (int j=0; j<m; j++) {
            if (a[0] == b[j]) {
                //直接把前面j-1个位置的元素删除了
                maxlcs[0][j] = 1;
            } else if (j != 0) {
                maxlcs[0][j] = maxlcs[0][j-1];
            }
        }
        //初始化第0列
        for (int i=0; i<n; i++) {
            if (a[i] == b[0]) {
                //直接把前面i-1个位置的元素删除就行
                maxlcs[i][0]=1;
            } else if (i != 0) {
                maxlcs[i][0] = maxlcs[i-1][0];
            }
        }

        //max_lcs(i, j)的值是比较完a[0..i] 和 b[0..j] 后的最长公共子串长度
        //(i-1,j) 要到 (i,j) 需要删除a[i-1]或者b[j]前加一个字符，不匹配，
        //(i,j-1) 到 (i,j) 是相同的道理
        //(i-1,j-1) 到 (i,j), 如果a[i]!=b[j] 就a[i-1]==b[j-1]的情况，如果a[i]==b[j] 就要增加一个最长公共子串长度
        //按行填表
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                if (a[i] == b[j]) {
                    maxlcs[i][j] = max(maxlcs[i-1][j-1]+1, maxlcs[i-1][j], maxlcs[i][j-1]);
                } else {
                    maxlcs[i][j] = max(maxlcs[i-1][j-1], maxlcs[i-1][j], maxlcs[i][j-1]);
                }
            }
        }
        return maxlcs[n-1][m-1];
    }

    /**
     * 三个数求最小值
     * @param x
     * @param y
     * @param z
     * @return
     * @author lijiewei
     * @date   2022/5/17 14:34
     */
    private int max(int x, int y, int z) {
        int maxv = Integer.MIN_VALUE;
        if (x > maxv) maxv = x;
        if (y > maxv) maxv = y;
        if (z > maxv) maxv = z;
        return maxv;
    }

    /**
     * 状态转移方程法求最长公共子串长度
     * 状态转移方程：max(max_lcs(i-1,j-1)+1, max_lcs(i-1, j), max_lcs(i, j-1))
     * 和 max(max_lcs(i-1,j-1), max_lcs(i-1, j), max_lcs(i, j-1))
     * @param a 数组a
     * @param n 数组a的长度
     * @param b 数组b
     * @param m 数组b的长度
     * @return
     * @author lijiewei
     * @date   2022/5/17 14:37
     */
    public int lcs2(char[] a, int n, char[] b, int m) {
        this.a = a;
        this.b = b;
        this.mem = new int[n][m];
        return max_lcs(n-1, m-1);
    }

    private char[] a;
    private char[] b;
    private int[][] mem;

    private int max_lcs(int i, int j) {
        if (i==0) {
            if (a[i] == b[j]) {
                //直接把前面j-1个位置的元素删除就行
                mem[i][j] = 1;
            } else if (j != 0) {
                mem[i][j] = mem[i][j-1];
            }
            return mem[i][j];
        } else if (j==0) {
            if (a[i] == b[j]) {
                //直接把前面i-1个位置的元素删除就行
                mem[i][j]=1;
            } else if (i != 0) {
                mem[i][j] = mem[i-1][j];
            }
            return mem[i][j];
        }


        if (mem[i][j]>0) {
            return mem[i][j];
        }
        if (a[i] == b[j]) {
            mem[i][j] = max(max_lcs(i-1,j-1)+1, max_lcs(i-1, j), max_lcs(i, j-1));
        } else {
            mem[i][j] = max(max_lcs(i-1,j-1), max_lcs(i-1, j), max_lcs(i, j-1));
        }
        return mem[i][j];
    }

}
